import org.junit.jupiter.api.Test;

public class reverseList {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        // cur指向反转的起点位置，pre指向前序节点
        ListNode cur = pre.next;
        for (int i = 0; i < right - left; i++) {
            ListNode removed = cur.next;
            cur.next = removed.next;
            // 头插法，pre.next才是头，cur会随着迭代相对位置接近队尾
            removed.next = pre.next;
            // removed.next = cur; 错误写法
            pre.next = removed;
        }
        return dummy.next;
    }

    @Test
    public void test() {
        int[] nodes = new int[] { 1, 2, 3, 4, 5 };
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        for (int i : nodes) {
            ListNode cur = new ListNode(i);
            pre.next = cur;
            pre = pre.next;
        }
        ListNode head = reverseBetween(dummy.next, 2, 4);
        StringBuilder res = new StringBuilder("[");
        while (head != null) {
            res.append(head.value + ",");
            head = head.next;
        }
        res.deleteCharAt(res.length() - 1).append("]");
        System.out.println(res.toString());
        System.out.println("000000000000000000000000000");
    }

}

class ListNode {

    int value;
    ListNode next;

    public ListNode() {
    }

    public ListNode(int value) {
        this.value = value;
    }

    public ListNode(int value, ListNode next) {
        this.value = value;
        this.next = next;
    }

}
